package _05_二叉树;

import java.util.Stack;

public class _333_最大BST子树 {

    public int largestBSTSubtree(TreeNode root) {
        return root == null? 0: getInfo(root).size;
    }

    // 获取以root为根节点的最大BST子树的信息
    public Info getInfo(TreeNode root) {
        if (root == null) return null;

        Info left = getInfo(root.left);
        Info right = getInfo(root.right);

        // 判断root和 left，right的关系
        if (left == null && right == null) {
            return new Info(root, 1, root.val, root.val);
        } else if (right == null) {
            return left;
        } else if (left == null) {
            return right;
        } else {
            // left，right不等于空
            if (left.root != root.left || right.root != root.right || root.val < left.max || root.val > right.min) {
                // 选择其中数量最大的
                return left.size > right.size? left: right;
            } else {
                return new Info(root, left.size + right.size + 1, left.min, right.max);
            }
        }
    }

    // 此函数的作用是，返回以root为根节点的最大BST子树的数量
    public int largestBSTSubtree1(TreeNode root) {
        // 方法是自顶而下的计算，判断有很多重复的地方
        if (root == null) return 0;
        BSTInfo info = isValidBST1(root);
        if (info.isBST) {
            return info.count;
        }
        // 要不然就返回左右子树的最大值
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree((root.right)));
    }

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long min, long max) {
        return root == null || root.val > min && root.val < max && isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }

    // 中序遍历，看是否为从大到小顺序
    private BSTInfo isValidBST1(TreeNode node) {
        Stack<TreeNode> stack = new Stack();
        TreeNode prev = null;
        int count = 0;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode treeNode = stack.pop();
                if (prev != null && treeNode.val <= prev.val) {
                    return new BSTInfo(false, -1);
                }
                prev = treeNode;
                count++;
                if (treeNode.right != null) {
                    node = treeNode.right;
                }
            }

        }
        return new BSTInfo(true, count);
    }

    private static class BSTInfo {
        boolean isBST;

        int count;

        public BSTInfo(boolean isBST, int count) {
            this.isBST = isBST;
            this.count = count;
        }
    }

    private static class Info {

        TreeNode root;

        int size = 1;

        int min;

        int max;

        public Info(TreeNode root, int size, int min, int max) {
            this.root = root;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }

}
